/**
 * FileName: Exercise1277.c
 * --------------------------------------------------------------------------------------------------------------
 * 12.77 Draw the binary search tree that results when you insert items with the keys `E A S Y` into
 * one initially empty tree, and insert items with the keys `Q U E S T I O N` into another initially empty tree,
 * then combine the result.
 * --------------------------------------------------------------------------------------------------------------
 */
#include <assert.h>
#include <stdlib.h>

typedef struct Item* Item;
typedef char Key;
typedef int Value;

#define key(A) (A->key)
#define less(A, B) (A < B)
#define eq(A, B) (A == B)
#define exch(A, B) { Item t = A; A = B; B = t; }
#define NULLitem NULL

struct Item {
    Key key;
    Value value;
};

typedef struct STnode* link;

struct STnode {
    Item item;
    link l;
    link r;
    int N;
};
link z;

/***********************************辅助函数部分*******************************/
link NEW(Item item, link l, link r, int N) {
    link x = malloc(sizeof(*x));
    x->item = item;
    x->l = l;
    x->r = r;
    x->N = N;
    return x;
}

int size(link h) {
    if (h == z) {
        return 0;
    }else {
        return h->N;
    }
}

void update_N(link h) {
    if (h != z) {
        h->N = size(h->l)+size(h->r)+1;
    }
}

/**
 * ---------------------------------------------------------------------------------------------------------
 * Program 12.11 Rotations in BSTs
 * ---------------------------------------------------------------------------------------------------------
 * These twin routines perform the rotation operation on a BST.
 * A right rotation makes the old root the right subtree of the new root (the old left subtree of the root).
 * A left rotation makes the old root the left subtree of the new root (the old right subtree of the root).
 *
 * For implementations where a count field is maintained in the nodes
 * (for example, to support `select`, as we will see in Section 14.9),
 * we need also to exchange the `count` fields in the nodes involved in the rotation (see Exercise 12.72).
 * ---------------------------------------------------------------------------------------------------------
 * 右旋
 * @param h
 * @return
 * 涉及3个链接和两个节点
 *
 * 这两个节点分别是：
 * - 旧根h
 * - 新根x，即h的左孩子
 *
 * 显然有：h的键大于等于x的键
 *
 * 这3个链接分别是：
 * - 原指向旧根的链接；
 * - 旧根指向新根的链接h->l;
 * - 新根的右孩子节点x->r;
 *
 * 右旋的本质是将旧根的左链接逆向
 */
link rotR(link h) {
    link x = h->l;
    h->l = x->r;
    x->r = h;
    update_N(h);
    update_N(x);
    return x;
}

/**
 * 左旋
 * @param h
 * @return
 * -----------------------------------------
 * 涉及3个链接和两个节点
 *
 * 这两个节点分别是：
 * - 旧根h
 * - 新根x，即h的右孩子
 *
 * 显然有：h的键小于等于x的键
 *
 * 这3个链接分别是：
 * - 原指向旧根的链接；
 * - 旧根指向新根的链接h->r;
 * - 新根的左孩子节点x->r;
 *
 * 左旋的本质是将旧根的右链接逆向
 */
link rotL(link h) {
    link x = h->r;
    h->r = x->l;
    x->l = h;
    update_N(h);
    update_N(x);
    return x;
}

/**
 * Program 12.12 Root insertion in BSTs
 * ----------------------------------------------------------------------------------
 * With the rotation functions in Program 12.11,
 * a recursive function that inserts a new node at the root of a BST is immediate:
 * - Insert the new item at the root in the appropriate subtree,
 * - then perform the appropriate rotation to bring it to the root of the main tree.
 * ----------------------------------------------------------------------------------
 * 在根部插入递归版
 * @param h 主树的根
 * @param v 待插入项
 * @return
 */
link insertT(link h, Item item) {
    if (h == z) {
        return NEW(item, z, z, 1);
    }
    Key v = key(item);
    if (less(v, key(h->item))) {
        h->l = insertT(h->l, item);
        h = rotR(h);
    }else {
        h->r = insertT(h->r, item);
        h = rotL(h);
    }
    return h;
}

/**
 * 在底部插入项
 * @param h
 * @param item
 * @return
 * -------------------------------------------
 * insertT是insertR的自适应版本
 *
 */
link insertR(link h, Item item) {
    if (h == z) {
        return NEW(item, z, z, 1);
    }
    Key v = key(item);
    Key t = key(h->item);
    if (less(v, t)) {
        h->l = insertR(h->l, item);
    }else {
        h->r = insertR(h->r, item);
    }
    update_N(h);
    return h;
}

/***********************************接口部分*******************************/
link STinit() {
    // 确保 z 只初始化一次
    static int z_initialized = 0;
    if (!z_initialized) {
        z = NEW(NULLitem, 0, 0, 0); // 确保z的l和r是NULL，而不是0
        z_initialized = 1;
    }
    return z; // 初始空树就是哨兵z
}

int STcount(link h) {
    return h->N;
}

/**
 * STinsert
 * @param h_ptr 指向树根的指针
 * @param item
 * 思路：
 * - 在底部插入
 */
void STinsert(link* h_ptr, Item item) {
    // 在底部插入(普通版本)
    *h_ptr = insertR(*h_ptr, item);
}


/**
 * Program 12.16 Joining of two BSTs
 * --------------------------------------------------------------------------------------------
 * If either BST is empty, the other is the result.
 * Otherwise,
 * - we combine the two BSTs by (arbitrarily) choosing the root of the first as the root,
 * root inserting that root into the second,
 * - then (recursively) combining the pair of left subtrees and the pair of right subtrees.
 * --------------------------------------------------------------------------------------------
 * @param a
 * @param b
 * @return
 */
link STjoin(link a, link b) {
    if (b == z) {
        return a;
    }
    if (a == z) {
       return b;
    }
    b = insertT(b, a->item);
    b->l = STjoin(a->l, b->l);
    b->r = STjoin(a->r, b->r);
    free(a);
    update_N(b);
    return b;
}
/***********************************测试部分*******************************/
Item create_item(Key key, Value value) {
    Item x = malloc(sizeof(*x));
    x->key = key;
    x->value = value;
    return x;
}

void test_join() {
    link a = STinit();
    assert(STcount(a) == 0);

    STinsert(&a, create_item('E', 1));
    STinsert(&a, create_item('A', 2));
    STinsert(&a, create_item('S', 3));
    STinsert(&a, create_item('Y', 4));

    link b = STinit();
    assert(STcount(b) == 0);

    STinsert(&b, create_item('Q', 1));
    STinsert(&b, create_item('U', 2));
    STinsert(&b, create_item('E', 3));
    STinsert(&b, create_item('S', 4));
    STinsert(&b, create_item('T', 5));
    STinsert(&b, create_item('I', 6));
    STinsert(&b, create_item('O', 7));
    STinsert(&b, create_item('N', 8));

    link c = STjoin(a, b);

    assert(size(c) == 12);
    //第1层
    assert(key(c->item) == 'E');
    //第2层
    assert(key(c->l->item) == 'A');
    assert(key(c->r->item) == 'S');
    //第3层
    assert(c->l->l == z);
    assert(key(c->l->r->item) == 'E');
    assert(key(c->r->l->item) == 'Q');
    assert(key(c->r->r->item) == 'Y');
    //第4层
    assert(c->l->r->l == z);
    assert(c->l->r->r == z);
    assert(key(c->r->l->l->item) == 'I');
    assert(key(c->r->l->r->item) == 'S');
    assert(key(c->r->r->l->item) == 'U');
    assert(c->r->r->r == z);
    //第5层
    assert(c->r->l->l->l == z);
    assert(key(c->r->l->l->r->item) == 'O');
    assert(c->r->l->r->l == z);
    assert(c->r->l->r->r == z);
    assert(key(c->r->r->l->l->item) == 'T');
    assert(c->r->r->l->r == z);
    //第6层
    assert(key(c->r->l->l->r->l->item) == 'N');
    assert(c->r->l->l->r->r == z);
    assert(c->r->r->l->l->l == z);
    assert(c->r->r->l->l->r == z);

}

int main(int argc, char *argv[]) {
    test_join();
    return 0;
}
